package NO6_Tree;

import java.util.Stack;

/**
 * 2025-08-18
 * 深度搜索一般方法
 */
public class DFSMain {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                3,
                new TreeNode(9),
                new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        preorderDFS(root);
    }


    /*----------------------- 递归-region -----------------------*/

    // 前序遍历（根-左-右）
    public static void preorderDFS(TreeNode root) {
        if (root == null) return;
        System.out.print(root.val + " "); // 访问根节点
        preorderDFS(root.left);           // 递归左子树
        preorderDFS(root.right);          // 递归右子树
    }

    // 中序遍历（左-根-右）
    public static void inorderDFS(TreeNode root) {
        if (root == null) return;
        inorderDFS(root.left);            // 递归左子树
        System.out.print(root.val + " "); // 访问根节点
        inorderDFS(root.right);           // 递归右子树
    }

    // 后序遍历（左-右-根）
    public static void postorderDFS(TreeNode root) {
        if (root == null) return;
        postorderDFS(root.left);          // 递归左子树
        postorderDFS(root.right);         // 递归右子树
        System.out.print(root.val + " "); // 访问根节点
    }
    /*----------------------- 递归-endregion -----------------------*/


    /*----------------------- 迭代-使用栈-region -----------------------*/
    // 前序遍历（迭代版）
    public static void preorderDFSIterative(TreeNode root) {
        if (root == null) return;

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");

            // 先压右子树，再压左子树
            if (node.right != null) stack.push(node.right);
            if (node.left != null) stack.push(node.left);
        }
    }

    // 中序遍历（迭代版）
    public void inorderDFSIterative(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();
            System.out.print(curr.val + " ");
            curr = curr.right;
        }
    }
    /*----------------------- 迭代-使用栈-endregion -----------------------*/
}
